//
// Created by 张朝辉 on 2023/10/10.
//

#include "npda.h"
#include <algorithm>
#include <iostream>

NPDA::NPDA(std::set<std::string> state_set, std::set<char> char_set, std::set<char> stack_charset,
           std::map<Tuple3, std::set<std::pair<std::string, std::string>>> rule_table, std::string start_state, char start_char,
           std::set<std::string> final_set)
           :state_set(state_set),char_set(char_set),stack_charset(stack_charset),rule_table(rule_table),
           start_state(start_state),start_char(start_char),final_set(final_set){}

/*
 * 对某一配置进行特定的某个状态转换操作，并返回新的配置
 */
auto NPDA::get_newID(ID id, std::pair<std::string, std::string> t) -> ID {
    id.q = t.first;          // 更新状态
    if(t.second == ""){
        id.g.pop();          // 弹出栈顶内容
    }
    // 和DPDA中的相关操作一样，如果t长度为1说明不进行栈的相关操作，长度大于1时说明有新的符号入栈
    if(t.second.length() > 1){
        id.g.pop();
        std::string str = t.second;
        std::reverse(str.begin(),str.end());
        for(auto &ch: str){          // 更新栈顶内容
            id.g.push(ch);
        }
    }
    return id;
}

/*
 * 将某个PDA的配置（ID）状态转换后的配置存入瞬时状态队列末尾并返回true，若无法进行状态转换则返回false
 */
auto NPDA::state_transition(ID id) -> bool {
    bool flag = false;
    auto it1 = rule_table.find(Tuple3{id.q,id.w[0],id.g.top()});
    if(it1 != rule_table.end() && id.w.length() != 0){                // 识别某个字符规则表中有相应规则
        for(auto &r: it1->second){
            std::string nw = id.w.length() == 1?"":id.w.substr(1,id.w.length()-1);    // 获取消耗一个字符后的字符串
            auto k = get_newID(ID{id.q,nw,id.g},r);        // 获取转换后的配置
            id_set.push(k);            // 压入瞬时队列
        }
        flag = true;
    }
    auto it2 = rule_table.find(Tuple3{id.q,'\0',id.g.top()});
    if(it2 != rule_table.end()){                       // 不消耗字符的情况下有对应规则
        for(auto &r: it2->second){
            auto k = get_newID(id,r);
            id_set.push(k);
        }
        flag = true;
    }
    return flag;
}

/*
 * 判断NPDA能否以终态方式接收某个字符串
 */
auto NPDA::isAccept_str(std::string str) -> bool {
    std::stack<char> s;
    s.push('#');
    id_set.push(ID{start_state,str,s});      // 将初始配置入队
    while (!id_set.empty()){
        if(!state_transition(id_set.front())){       // 如果没有规则导致状态转换出错
            if(final_set.find(id_set.front().q) != final_set.end() && id_set.front().w.empty()){
                // 当前状态为接受状态并且已经识别完整个字符串
                return true;
            }
        }
        id_set.pop();
    }
    return false;
}

auto NPDA::description() -> void {
    std::cout<<"-------------------------------------当前NPDA详情----------------------------------------"<<std::endl;
    std::cout<<"状态集：{ ";
    for(auto &s: state_set){
        std::cout<<s<<" ";
    }
    std::cout<<"}"<<std::endl;
    std::cout<<"字符集：{ ";
    for(auto &s: char_set){
        std::cout<<s<<" ";
    }
    std::cout<<"}"<<std::endl;
    std::cout<<"栈字符集：{ ";
    for(auto &s: stack_charset){
        std::cout<<s<<" ";
    }
    std::cout<<"}"<<std::endl;
    std::cout<<"开始状态："<<start_state<<std::endl;
    std::cout<<"栈起始符号："<<start_char<<std::endl;
    std::cout<<"接受状态集：{ ";
    for(auto &s: final_set){
        std::cout<<s<<" ";
    }
    std::cout<<"}"<<std::endl;
    std::cout<<"状态转换表：{ ";
    for(auto &r: rule_table){
        std::cout<<"δ("<<r.first.q<<","<<r.first.a<<r.first.x<<") = { ";
        for(auto &s: r.second){
            std::cout<<"("<<s.first<<","<<s.second<<") ";
        }
        std::cout<<" }\t";
    }
    std::cout<<"}"<<std::endl;
    std::cout<<"----------------------------------------------------------------------------------------"<<std::endl;
}

